package com.wp.leetCode;

/**
 * You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed,
 * the only constraint stopping you from robbing each of them is that adjacent houses have security system connected
 * and it will automatically contact the police if two adjacent houses were broken into on the same night.
 * Given a list of non-negative integers representing the amount of money of each house, determine the
 * maximum amount of money you can rob tonight without alerting the police.
 */

/**
 * 1.记忆法搜索递归
 * 2.递推
 */
class HouseRobber {
//     public int[] maxValue;
    
//     public int rob(int[] nums) {
//         int size=nums.length;
//         maxValue=new int[size];
//         for(int i=0;i<size;i++){
//             maxValue[i]=-1;
//         }
//         return getMax(size-1,nums);
//     }
    
//     public int getMax(int idx,int[] nums){
//         if (idx < 0){
//             return 0;
//         }
//         if(maxValue[idx] >= 0){
//             return maxValue[idx];
//         }
//         maxValue[idx] = Math.max(nums[idx]+getMax(idx-2,nums),getMax(idx-1,nums));
//         return maxValue[idx];
//     }

        public int[] maxValue;
    
        public int rob(int[] nums){
            if(nums.length==0){
                return 0;
            }
            if(nums.length==1){
                return nums[0];
            }
            maxValue=new int[nums.length];
            maxValue[0]=nums[0];
            maxValue[1]=Math.max(nums[0],nums[1]);
            for(int i=2;i<nums.length;i++){
                maxValue[i]=Math.max(nums[i]+maxValue[i-2],maxValue[i-1]);
            }
            return maxValue[nums.length-1];
        }
}